package leetcode;

import java.util.ArrayList;
import java.util.List;

public class LeetCode95 {
    List<TreeNode> result = new ArrayList<>();

    int n;

    // 1-n的全排列 然后检查数是否重复
    public List<TreeNode> generateTrees(int n) {
        int[] array = new int[n];
        this.n = n;
        for (int i = 1; i <= n; i++) {
            int[] clone = array.clone();
            clone[i - 1] = 1;
            TreeNode root = new TreeNode(i);
            helper(1, root, clone);
        }
        return result;
    }

    private void helper(int useCount, TreeNode root, int[] array) {
        if (useCount == array.length - 1) {

        } else {
            for (int i = 1; i <= n; i++) {
                if (array[i - 1] == 0) {
                    int[] clone = array.clone();
                    clone[i - 1] = 1;
                    addTreeNode(root, i);
                    helper(useCount + 1, root, clone);
                }
            }
        }
    }

    private void addTreeNode(TreeNode root, int val) {
        TreeNode node = new TreeNode(val);
        TreeNode current = root, pre = root;
        while (current != null) {
            pre = current;
            if (current.val < val)
                current = current.right;
            else
                current = current.left;
        }
        if (pre.val < val)
            pre.right = node;
        else
            pre.left = node;
    }
//------------------------------------------------------------------
}
